package XZK010104AND002;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 数组常见算法与逻辑训练（数组+逻辑）
 *
 * @author bing.z 2021/5/27 10:09
 **/
public class Demo {
    public static void main(String[] args) {
        /**
         * 1、查找某个整数
         * 定义一个长度为 10 的整型数组 nums ，循环输入 10 个整数。 然后将输
         * 入一个整数，查找此整数，找到 输出下标， 没找到给出提示。
         */
        solveNo1();

        /**
         * 2、找出数组的最值
         * 定义一个长度为 10 的整型数组 nums ，循环输入 10 个整数。输出数组
         * 的最大值、最小值。
         */
        solveNo2();

        /**
         * 3、两数之和
         * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和
         * 为目标值的那两个整数，并输出他们的数组下标
         * 假设每种输入只会对应一个答案，不能重复利用这个数组中同样的元素。
         * 示例:
         * 给定 nums = [2, 7, 11, 15], target = 9
         * 因为 nums[0] + nums[1] = 2 + 7 = 9
         * 所以输出 0，1
         */
        solveNo3();

        /**
         * 4、排序并查找
         *
         * 对数组{1，3，9，5，6，7，15，4，8}进行排序，然后使用二分查找元素
         * 6 并输出排序后的下标。
         */
        solveNo4();


        /**
         * 5、移动零
         * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时
         * 保持非零元素的相对顺序。
         * 示例:
         * 输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
         */
        solveNo5();
    }

    private static void solveNo5() {
        // 冒泡排序思路
        int tmp;
        int[] arr = {0, 1, 0, 3, 12};
        for (int i = 0; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] != 0 && arr[j - 1] == 0) {
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
                j--;
            }
        }
        for (int v : arr) {
            System.out.print(v + " ");
        }
        System.out.println();
    }

    private static void solveNo4() {
        int[] arr = {1, 3, 9, 5, 6, 7, 15, 4, 8};
        // 冒泡排序
        int tmp;
        for (int i = arr.length - 1; i >= 0; i--) {
            boolean enter = false;
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    enter = true;
                }
            }
            if (!enter) {
                break;
            }
        }
        for (int v : arr) {
            System.out.print(v + " ");
        }
        System.out.println();
        // 二分查找
        int target = 6;
        int pos = -1;
        int l = 0, r = arr.length;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (arr[mid] == target) {
                pos = mid;
                break;
            } else if (arr[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(target + " 在数组中的下标为 " + pos);
    }

    private static void solveNo3() {
        int[] nums = {2, 7, 11, 15};
        int target = 13;
        Map<Integer, Integer> posMap = new HashMap<>();
        boolean find = false;
        for (int i = 0; i < nums.length; i++) {
            if (posMap.containsKey(target - nums[i])) {
                find = true;
                System.out.println(posMap.get(target - nums[i]) + "," + i);
                break;
            }
            posMap.put(nums[i], i);
        }
        if (!find) {
            System.out.println("未找到匹配结果!");
        }
    }

    private static void solveNo2() {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入十个数（以空格隔开）：");
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        int emax = Integer.MIN_VALUE, emin = Integer.MAX_VALUE;
        for (int e : arr) {
            emax = Math.max(emax, e);
            emin = Math.min(emin, e);
        }
        System.out.println("最大数为 " + emax + ",最小数为 " + emin);
    }

    private static void solveNo1() {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入十个数（以空格隔开）：");
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println("请输入你需要查找的数：");
        int ele = scanner.nextInt();
        boolean find = false;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == ele) {
                find = true;
                System.out.println(ele + " 在数组中下标为：" + i);
                break;
            }
        }
        if (!find) {
            System.out.println("数组中找不到元素 " + ele);
        }
    }
}
